package 反转链表;

import 反转链表.ListNode;

public class Solution {
    public ListNode reverseList(ListNode head) {
        // 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表
        // 采用头插法，原地逆转

        if ( head == null ){
            return null;
        }

        // 1.虚拟头节点
        ListNode virtualHead = new ListNode();
        virtualHead.next = null;
        // 指向下一个待逆转的节点，防止断链
        ListNode p = new ListNode();
        p = head.next;

        // 2.头插法
        while ( head != null ){
            head.next = virtualHead.next;
            virtualHead.next = head;
            head = p;
            if ( p != null )
                p = p.next;
        }

        // 3.返回反转后的链表
        return virtualHead.next;
    }

}